//************************************************************
//    > File Name: reverse-linked-list.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月21日 11:02:22
//***********************************************************
//lintcode #35
#include<bits/stdc++.h>
using namespace std;
class ListNode{
	public:
		int val;
		ListNode *next;
		ListNode(int val=-1){
			this->val=val;
			this->next=NULL;
		}
};
ListNode *reverse(ListNode *head){
	ListNode *p=NULL;
	for(ListNode *t;head;){
		t=head->next;
		head->next=p;
		p=head;
		head=t;
	}
	return p;
}
ListNode *create(vector<int> &v){
	ListNode H;
	int i=0;
	for(ListNode *p=&H;i<v.size();++i){
		p->next=new ListNode(v[i]);
		p=p->next;
	}
	return H.next;
}
void clean(ListNode *l){
	for(ListNode *t;l;){
		t=l;
		l=l->next;
		delete t;
	}
}
int main(){
	vector<int> v={
		1,2,3,4,5,6,7,8,9
	};
	ListNode *m=create(v);
	ListNode *n=reverse(m);
	for(;n;n=n->next)
		cout<<n->val<<" ";
	cout<<endl;
	clean(n);

}
